/**
 * @file tree.hpp
 * @brief 树结构实现
 */

#pragma once
#include <carbon/core/alloc.h>

CARBON_NS_BEGIN

/// @brief 二叉树节点基类
struct BinTreeNodeBase { 
    BinTreeNodeBase *m_parent;   // 父节点
    BinTreeNodeBase *m_left;     // 左子节点
    BinTreeNodeBase *m_right;    // 右子节点
};

/// @brief 二叉树头
struct BinTreeHeader {
    BinTreeNodeBase *m_root;     // 根节点
    size_t           m_count;    // 节点数
};

/// @brief 二叉树节点类
/// @tparam T 节点数据类型
template <typename T>
struct BinTreeNode : BinTreeNodeBase {
    T m_data;
};

template <typename T>
struct BinTreeIterator {};

template <typename T>
struct BinTreeConstIterator {};

template <typename Compare, typename Alloc>
struct BinTreeImpl {
    Alloc           m_alloc;
    Compare         m_comp;
    BinTreeHeader   m_header;
}; 

template<typename K, typename V>
struct Pair {
    K first;
    V second;
};


/// @brief 二叉搜索树类
/// @tparam T       节点数据类型
/// @tparam Compare 比较函数
/// @tparam Alloc   节点内存分配器
template <typename K, typename V, typename KeyCompare, typename Alloc>
class BinSearchTree {
public:
    using Key = K;
    using Value = V;
    using Node = BinTreeNode<Pair<K, V>>;
    using NodePtr = Node *;
    using Allocator = Alloc;
    using Iterator = BinTreeIterator<Pair<K, V>>;
    using ConstIterator = BinTreeConstIterator<Pair<K, V>>;

public:

    bool empty() const noexcept { return size() == 0; }
    size_t size() const noexcept { return m_impl.m_header.m_count; }

    Iterator begin() noexcept;
    Iterator end() noexcept;

    ConstIterator begin() const noexcept;
    ConstIterator end() const noexcept;

    Iterator find(const Key &k) noexcept;
    ConstIterator find(const Key& k) const noexcept;

    Iterator insert(const Pair<K, V> &data);
    Iterator insert(Pair<K, V> &&data);

    void    erase(const Iterator &it);
    void    erase(const ConstIterator &it);
    void    erase(const Key &k);

private:
    BinTreeImpl<KeyCompare, Alloc> m_impl;
}; // BinSearchTree

CARBON_NS_END 
